\chapter{Related work}
In this chapter, we will provide an overview of several approaches that made an attempt on optimal auction design problem, which are currently mainstream approach in this field. For each approach, different game settings will be initialized. Since each setting has its own convenience when using it's own notations, we will apply the original notations when describing these works, with a few more words describing it.
\section{Myerson's optimal auction design}
In the introduction part, we mentioned that Myerson's result in 1981 has an remarkable influence to the field of optimal auction design. Here we make a brief study about the simplest case, in which there is only one auctioneer selling only one item, to a set of prospective buyers who might be willing to pay for the item, and see how the optimal auction is designed.

\subsection{Game Setting and Basic definition}
In this game, as above mentioned, it's assume that there is only one seller with only one single object to sell. He faces $n$ bidders, or potential buyers, numbered $1, 2, \ldots, n$. Let $N$ represent the
set of bidders, so that
\begin{equation}
N = \{ 1, \ldots, n\}.
\end{equation}
The seller does not have any information about how much price the various bidders are willing to pay for the object, which here we use quantity $t_i$ to denote bidder $i$'s valuation for the object. To clarify, $t_i$ is the maximum amount of price that bidder $i$ will be willing to pay for the object. So here assumptions are made  about the valuations of bidder $i$ that it can be described by a continuous probability distribution over a certain and finite interval. See below for a formal definition of the distribution.

Set $a_i$ as the lowest possible value for bidder $i$ which might pay for the object, and $b_i$ as the highest possible value for bidder $i$ which might pay for the object. To characterize, let function $f_i : [a_i, b_i] \rightarrow \mathbb{R}_+$ be the probability density function for $i$'s value estimate $t_i$. It is assumed that $-\infty < a_i < b_i < +\infty$, as well as $\forall t_i \in [a_i, b_i], f_i(t_i) > 0$. Also assumed is that $f_i$ is continuous on the interval $[a_i, b_i]$. Here the notation $F_i:[a_i, b_i] \rightarrow [0,1]$ is introduced to be the cumulative distribution function corresponding to the density function $f_i$, thus the following equation stands:
\begin{equation}
F_i(t_i) = \int_{a_i}^{t_i} f_i(s_i) ds_i
\end{equation}
It is easy to notice that $F_i(t_i)$ is the seller's assessment of the probability that bidder $i$ has a value estimate of $t_i$ or less.

Denote $T$ as the set of all possible combinations of bidder's value estimates:
\begin{equation}
T = [a_1, b_1] \times \cdots \times [a_n, b_n]
\end{equation}
Also, the notation $T_{-i}$ is introduced to denote the set of all possible combinations of value estimates which might be held by bidders other than $i$, just as follows:
\begin{equation}
T_{-i} = \times_{j\in N, j \neq i}[a_j, b_j]
\end{equation}
To describe the joint distribution under the setting that all the distributions are independent, use $f$ to denote the joint density function defined as follows:
\begin{equation}
f(t) = \prod_{j\in N} f_j(t_j)
\end{equation}
For the similar idea, define $f_{-i}(t_{-i})$ to be the density function on the distribution $T_{-i}$
\begin{equation}
f_{-i}(t_{-i}) = \prod_{j\in N, j\neq i} f_j(t_j)
\end{equation}
For the bidders, it is assumed that there exist $n$ revision effect functions $e_j: [a_i, b_i] \rightarrow \mathbb{R}$, which means if other bidder $i$ gets the information about the bidder $j$'s valuation estimation, then this bidder $i$ will change his own valuation to 
\begin{equation}
v_i(t) = t_i + \sum_{j\in N, j \neq i} e_j(t_j)
\end{equation}
To complement, denote $s_i$ as the claimed value estimate while $t_i$ is the true value estimate.
\subsection{Various kinds of Mechanisms along with restrictions}
First we introduce the definition of direct revelation mechanisms.

In a direct revelation mechanism, the bidders simultaneously and confidentially announce their value estimates to the seller; and the seller then determines who gets the object and how much each bidder must pay. Thus, a direct revelation mechanism can be described by a pair of outcome functions $(p, x)$. We can again review this procedure: first the seller will announce a mechanism. This mechanism will generate allocations to each bidders, using valuation estimates $t = (t_1, \cdots, t_n)$ as input. Then the bidders commits their valuation estimates at a time, collecting together is the previous mentioned valuation estimate $t$. Then the seller will release the allocation, and the revenue can thus be calculated. 

Now let's take a look at the definition of feasible auction mechanism. Generally speaking, a feasible auction mechanism must meet three requirements: individually rational, incentive compatible and the allocation to an item should be reasonable(here reasonable means the sum of the  probability that an item is allocated to a certain set of bidders should be less than $1$).

Here we presents the revelation principle without proof, which can replace the feasible auction mechanisms with an equivalent one.
\begin{thm}
Given any feasible auction mechanism, there exists an equivalent feasible direct revelation mechanism which gives to the seller and all bidders the same utilities as in the given mechanism. 
\end{thm}
Using this revelation principle, we may assume that the seller only considers auction mechanisms in a certain class where revelation principle is applied.

As indicated in the previous section, for a bidder $i$, his value estimate information is private to the seller, as well as other bidders. There are two general reasons why this assumption is reasonable. First, the bidder's personal preferences might be
unknown to the other agents (for example, if the object is a painting, the others might
not know how much he really enjoys looking at the painting). Second, the bidder
might have some special information about the intrinsic quality of the object (he might
know if the painting is an old master or a copy).
\subsection{optimal auction conditions}
Here we present a lemma that obtains optimal auction with some simple conditions.
\begin{lem}
Suppose that $p : T \rightarrow \mathbb{R}^n$ maximizes
\begin{equation}
\int_T(\sum_{i\in N}(t_i - e_i(t_i) - \frac{1-F_i(t_i)}{f_i(t_i)} - t_0)p_i(t))f(t)dt
\end{equation}
and the feasible condition is satisfied. If we set $x_i(t)$ as follows:
\begin{equation}
x_i(t) = p_i(t)v_i(t) - \int_{a_i}^{t_i}p_i(t_{-i}, s_i)ds_i, \forall i \in N, \forall t \in T
\end{equation}
Then $(p, x)$ represents an optimal auction.
\end{lem}
Via this lemma, we can obtain the following Revenue-Equivalence Theorem.
\begin{thm}
The auctioneer's expected utility from a feasible auction mechanism is fully determined by the probability function $p$ along with the numbers $U_i(p,x,a_i)$ for all $i$, where $U_i$ denote the utility for bidder $i$.
\end{thm}

\section{Multidimensional Mechanisms}
\subsection{Overview of this approach}
In this approach, strong characterization results are obtained for the set of all feasible single-item mechanisms (for independent bidders), as well as for the set of all feasible multiple-item mechanisms when the bidders have arbitrarily correlated additive valuations over bundles of items (but there is no correlation across bidders). This characterization result is based on obtaining novel, constructive proofs of Border's theorem \cite{border1991implementation} and recent extensions of this theorem \cite{border2007reduced},\cite{che2011generalized}. Using these constructive
proofs and our characterization result, revenue-optimal, Bayesian Incentive Compatible
(BIC) mechanisms are obtained in multi-item multi-bidder settings, when each bidder has arbitrarily correlated
values over the items and additive valuations over bundles of items, and the bidders are independent.
This mechanisms run in time polynomial in the total number of bidder types. This running
time is polynomial in the number of bidders, but potentially exponential in the number of items.
The running time to polynomial in both the number of items and the number of
bidders is improved by using recent structural results on optimal BIC auctions in symmetric settings \cite{schrijver2003combinatorial}.
Also referred in this approach is a generalization of Border's theorem to the multi-item setting where values are arbitrarily correlated across items or bidders, and bidders have additive valuations with hard demand constraints, and provide a multi-commodity flow interpretation of this problem. In addition, this generalization holds for a much broader class of feasibility constraints. Simply put, our generalization holds in all instances where the feasibility constraints can be written as a system of inequalities that are linear in allocation
marginals. This includes feasibility constraints that are the intersection of any two matroids, as well as many other set systems \cite{schrijver2003combinatorial}.
\subsection{Game Setting and Basic definition}
In this game, it is assumed that every bidder has a type $t_i \in T_i$, where $T_i$ is the candidate set for the $i$-th bidder. For the bidder with the same type, they share the same valuations. The joint type profile of the bidders is sampled from
some known, joint distribution $D$ over $\times_i T_i$. According to the Revelation Principle, every
auction is strategically equivalent to one where bidders submit not generic bids, but truthfully
report their exact type. Thus we can focus our attention on mechanisms where the bid space of bidder $i$ is just $T_i$. It is clear that this is a reduced form of the optimal mechanism, which only consider the distributions that are discrete. One thing should be point out is that in this configuration, independence is not required: the valuations of all the bidders can be correlated.
\subsection{A summary of the results}
Here we summarize the novel works about multi-dimensional optimal auction design.
\begin{enumerate}
\item If a reduced form auction for independent bidders and a single item is given to us as input, we can efficiently determine if the auction is feasible or not. 
\begin{itemize}
\item If it is feasible, we efficiently compute an efficient process that implements it
\item If not feasible, we efficiently provide a hyperplane separating it from the set of feasible mechanisms.
\end{itemize}
Since for the multi-item case, we have a setting that additive property and independent bidders with arbitrary correlated values of the bidders property, this can be generalized to multi-item case.
\item Every feasible reduced form auction for a single item
and independent bidders can be implemented as a distribution over hierarchical mechanisms. Using
these theorems we obtain a clean, characterization of the allocation rule of all multidimensional
mechanisms for multi-item settings with independent, additive bidders and arbitrary correlation
in the values of each bidder for the items.
\item we can transform
the marginal probabilities $\Pi$ of a reduced form into virtual $\Pi$ such that the total ordering of the
types (across different bidders) induced by the virtual $\Pi$ allows us to, in linear time, verify the
feasibility of a reduced form auction or output a hyperplane separating it from the set of feasible
reduced forms.
\item generalization of Border's Theorem to a broad class
of feasibility constraints that includes the case of many items, many additive bidders with hard
demand constraints, and arbitrary value correlation across items or bidders
\end{enumerate}
\section{Optimal Deterministic Auctions with Correlated Priors}
\subsection{Motivation}
Myerson's work leaves open the case that when valuations from the bidders are correlated. In subsequent work, \cite{cremer1988full},\cite{cremer} considered correlated valuations and solve the problem in case that auctions are only required to be interim individually rational. Despite the elegance of their result, the fact that bidders may be charged merely for participating in the auction-lottery has been point out to be rendering the auction impractical, especially for settings where agents may easily cancel their participation after the auction is conducted. It is therefore of tantamount importance to consider the question of designing the optimal ex post individually rational auction for correlated valuations. This is the question here considered, and in a sense completely answer.
\subsection{Game Setting and Basic definition}
Imagine $n$ bidders seeking an indivisible good offered in auction. Assume that each bidder has a private valuation $v_i$ for the item and that bidders' valuation are drawn from some joint distribution over $[0,1]^n$ whose density function denoted here with $\Phi(v)$. Here both discrete and continuous $\phi$ are considered.Discrete distributions are the source of the combinatorial insights underlying
our approach, while continuous distributions provide continuity with the spirit and methodology
of Myerson's paper, another important source of inspiration.

In this game, designing auction that maximize the auctioneer's profit is the goal. To speak more formally, an auction consists of an allocation rule denoted by $x_i(v)$, the probability the probability of bidder $i$ getting allocated the item, and a payment rule denoted by $p_i(v)$ which is the price paid by bidder $i$. Here attentions will be focused on deterministic mechanisms so that $x_i(v)\in \{0,1\}$. The goal here is to maximize the auctioneer's expected profit $\sum_{i=1}^n E[\phi(v)p_i(v)]$.
\subsection{A summary of the results}
In this work, a complexity-theoretic view of general, correlated valuations cases of Myerson's single-item auctions is provided.
It is pointed out that the optimal auction design problem can
be reduced essentially to a maximum weighted independent set problem in a particular graph whose vertices are all possible tuples of valuations (for the continuous case an uncountable set). If the distribution is discrete, this is an ordinary graph-theoretic problem; no such combinatorial characterization had been known, and this had been the main difficulty in developing an algorithmic and complexity-theoretic understanding of the problem. For discrete
distributions, this leads directly to an efficient algorithm in the case of two bidders, where the
graph is bipartite, while in the case of three or more bidders NP-completeness prevails. For continuous distributions, a duality characterization through a
Monge-Kantorovich-like problem \cite{evans1997partial} is proved, and from this a fully polynomial approximation scheme for two bidders when the distribution is continuous enough and accessible through an oracle 
plus, as an aside, a $\frac{2}{3}$ approximation for three bidders, improving the previously best known approximation of \cite{ronen2001approximating}.

\section{Summary of this chapter}
In this chapter, we made an overview of several approaches, which dealt with the optimal auction design problem in different aspects. Although each approach only handled a part of the optimal auction design problem --- in other words, there is no approach that perfectly solved this problem currently, and it is proved to be an NP-hard problem, these approaches can work in certain cases in the real auction and pricing situation. Also, these works has broadened our minds in this field and we can learn a lot from these outstanding works.